DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2022.16

Automorphisms of Random Trees

Authors: Christoffer Olsson and Stephan Wagner

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract

We study the size of the automorphism group of two different types of random trees: Galton-Watson trees and Pólya trees. In both cases, we prove that it asymptotically follows a log-normal distribution. While the proof for Galton-Watson trees mainly relies on probabilistic arguments and a general result on additive tree functionals, generating functions are used in the case of Pólya trees.

Cite as

Christoffer Olsson and Stephan Wagner. Automorphisms of Random Trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{olsson_et_al:LIPIcs.AofA.2022.16,
  author =	{Olsson, Christoffer and Wagner, Stephan},
  title =	{{Automorphisms of Random Trees}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.16},
  URN =		{urn:nbn:de:0030-drops-161026},
  doi =		{10.4230/LIPIcs.AofA.2022.16},
  annote =	{Keywords: random tree, Galton-Watson tree, P\'{o}lya tree, automorphism group, central limit theorem}
}

Search Results

Documents authored by Olsson, Christoffer

Automorphisms of Random Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message